﻿#define _CRT_SECURE_NO_WARNINGS 1
/**给定一个整数数组nums，按升序排序，数组中的元素各不相同。
nums数组在传递给search函数之前，会在预先未知的某个下标 t（0 <= t <= nums.length-1）上进行旋转，让数组变为[nums[t], nums[t+1], ..., nums[nums.length-1], nums[0], nums[1], ..., nums[t-1]]。
比如，数组[0,2,4,6,8,10]在下标2处旋转之后变为[6,8,10,0,2,4]
现在给定一个旋转后的数组nums和一个整数target，请你查找这个数组是不是存在这个target，如果存在，那么返回它的下标，如果不存在，返回-1
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @param numsLen int nums数组长度
* @param target int整型
* @return int整型
*/
//int search(int* nums, int numsLen, int target) {
//	// write code here
//	int i = 0;
//	for (i = 0; i<numsLen; i++)
//	{
//		if (nums[i] == target)
//		{
//			return i;
//		}
//	}
//	return -1;
//}







//class Solution {
//public:
//	/**
//	*实现函数 int sqrt(int x).
//	计算并返回x的平方根（向下取整）
//	* @param x int整型
//	* @return int整型
//	*/
//	int sqrt(int x) {
//		// write code here
//		if (x == 1 || x == 0)
//		{
//			return x;
//		}
//		int l = 0;
//		int r = x;
//		int res = -1;
//		while (l <= r)
//		{
//			int mid = l + (r - l) / 2;
//			if ((long long)mid*mid <= x)
//			{
//				res = mid;
//				l = mid + 1;
//			}
//			else
//			{
//				r = mid - 1;
//			}
//		}
//		return res;
//	}
//};







//给定一个球体的半径，计算其体积。其中球体体积公式为 V = 4 / 3 * πr3，其中 π = 3.1415926。
//#include <stdio.h>
//int main()
//{
//	double pi = 3.1415926;
//	float r = 0.0;
//	scanf("%f", &r);
//	double v = (4.0 / 3)*pi*(r*r*r);
//	printf("%.3f\n", v);
//	return 0;
//}








/**给你一个n（1\leq n\leq10^51≤n≤10 5），
和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，
求该序列的最大子序列和（挑选出的子序列可以为空）。
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算
* @param n int整型 数组的长度
* @param array int整型一维数组 长度为n的数组
* @param arrayLen int array数组长度
* @return long长整型
*/
//long long subsequence(int n, int* array, int arrayLen) {
//	// write code here
//	long long max = 0, max1 = 0, tmp = 0;
//	for (int i = 0; i<n; i++)
//	{
//		if (max1 + array[i]>max)
//		{
//			tmp = max;
//			max = max1 + array[i];
//			max1 = tmp;
//		}
//		else
//		{
//			max1 = max;
//		}
//	}
//	return max;
//}







/**给定一个数组，请你编写一个函数，返回该数组排序后的形式。
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @param arrLen int arr数组长度
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
//void sort(int *arr, int left, int right)
//{
//	if (left<right)
//	{
//		int i = left;
//		int j = right;
//		int tmp = arr[i];
//		while (i<j)
//		{
//			while (arr[j] >= tmp&&i<j)
//			{
//				j--;
//			}
//			arr[i] = arr[j];
//			while (arr[i] <= tmp&&i<j)
//			{
//				i++;
//			}
//			arr[j] = arr[i];
//		}
//		arr[i] = tmp;
//		sort(arr, left, i - 1);
//		sort(arr, i + 1, right);
//	}
//}
//int* MySort(int* arr, int arrLen, int* returnSize) {
//	// write code here
//	sort(arr, 0, arrLen - 1);
//	*returnSize = arrLen;
//	return arr;
//}







/**给定一个整形数组arr，已知其中所有的值都是非负的，
将这个数组看作一个容器，请返回容器能装多少水。
* max water
* @param arr int整型一维数组 the array
* @param arrLen int arr数组长度
* @return long长整型
*/
//long long maxWater(int* arr, int arrLen) {
//	// write code here
//	long long cnt = 0;
//	int le = 0, rig = arrLen - 1, left = 0, right = 0, val = 0;
//	while (le <= rig)
//	{
//		if (left >= right)
//		{
//			if (arr[rig] == right)
//			{
//				rig--;
//				continue;
//			}
//			if ((val = arr[rig--])>right)
//			{
//				right = val;
//				continue;
//			}
//			cnt += right - val;
//			continue;
//		}
//		if (arr[le] == left)
//		{
//			le++;
//			continue;
//		}
//		if ((val = arr[le++])>left)
//		{
//			left = val;
//			continue;
//		}
//		cnt += left - val;
//	}
//	return cnt;
//}







/**已知int一个有序矩阵mat，
同时给定矩阵的大小n和m以及需要查找的元素x，
且矩阵的行和列都是从小到大有序的。
设计查找算法返回所查找元素的二元数组，
代表该元素的行号和列号(均从零开始)。保证元素互异。
*
* @param mat int整型二维数组
* @param matRowLen int mat数组行数
* @param matColLen int* mat数组列数
* @param n int整型
* @param m int整型
* @param x int整型
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
//int* findElement(int** mat, int matRowLen, int* matColLen, int n, int m, int x, int* returnSize) {
//	// write code here
//	int *a = (int *)malloc(sizeof(int) * 2);
//	int i = 0;
//	int j = *matColLen - 1;
//	while (i<n&&j >= 0)
//	{
//		if (mat[i][j]<x)
//		{
//			i++;
//		}
//		else if (mat[i][j]>x)
//		{
//			j--;
//		}
//		else
//		{
//			a[0] = i;
//			a[1] = j;
//			*returnSize = 2;
//			break;
//		}
//	}
//	return a;
//}







/**给定一个非负整数 NN，返回 N!N! 结果的末尾为 00 的数量。
N!N! 是指自然数 NN 的阶乘,即:N!=1*2*3…(N-2)*(N-1)*NN!=1∗2∗3…(N−2)∗(N−1)∗N。
* the number of 0
* @param n long长整型 the number
* @return long长整型
*/
//long long thenumberof0(long long n) {
//	// write code here
//	long long max = 0;
//	while (n)
//	{
//		max += n / 5;
//		n /= 5;
//	}
//	return max;
//}







/**以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
（字符串长度不大于10000，保证字符串仅由'0'~'9'这10种字符组成
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
//char* solve(char* s, char* t) {
//	// write code here
//	int len1 = strlen(s);
//	int len2 = strlen(t);
//	int len = len1 + len2;
//	char* res = (char*)malloc(sizeof(char)*len);
//	int *ans = (int *)calloc(sizeof(int), len);
//	int i, j, k;
//	for (i = 0; i<len1; i++)
//	{
//		for (j = 0; j<len2; j++)
//		{
//			k = len - (len1 - i + len2 - j - 1);
//			ans[k] += (s[i] - '0')*(t[j] - '0');
//		}
//	}
//	for (i = len - 1; i>0; i--)
//	{
//		ans[i - 1] += ans[i] / 10;
//		res[i] = ans[i] % 10 + '0';
//	}
//	res[0] = ans[0] + '0';
//	if (*res == '0')
//	{
//		res = &res[1];
//	}
//	return res;
//}








/**已知一个背包最多能容纳物体的体积为V
现有n个物品第i个物品的体积为v_iv i
第i个物品的重量为w_iw i
求当前背包最多能装多大重量的物品
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算01背包问题的结果
* @param V int整型 背包的体积
* @param n int整型 物品的个数
* @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
* @param vwRowLen int vw数组行数
* @param vwColLen int* vw数组列数
* @return int整型
*/
//#define max(x,y) (x>y)?x:y
//int knapsack(int V, int n, int** vw, int vwRowLen, int* vwColLen) {
//	// write code here
//	int arr[210][210] = { 0 };
//	int wei = V;
//	int i, j;
//	for (i = 1; i <= n; i++)
//	{
//		for (j = 1; j <= V; j++)
//		{
//			if (j >= vw[i - 1][0])
//			{
//				arr[i][j] = max(arr[i - 1][j - vw[i - 1][0]] + vw[i - 1][1], arr[i - 1][j]);
//			}
//			else
//			{
//				arr[i][j] = arr[i - 1][j];
//			}
//		}
//	}
//	return arr[i - 1][j - 1];
//}